package leetcode.code;

import java.util.ArrayList;
import java.util.List;

public class Solution118 {

	public List<List<Integer>> generate(int numRows) {
		int len = (numRows + 1) * numRows / 2; // 总数量
		int[] arr = new int[len]; // 三角数据
		arr[0] = 1; // 第一个数据1
		List<List<Integer>> ans = new ArrayList<>(); // 答案
		List<Integer> row = new ArrayList<>();// 每一行
		row.add(1);
		ans.add(row);
		int off = 1;// 当前行之前一共多少个数, 偏移量
		for (int i = 2; i <= numRows; i++) {
			row = new ArrayList<>();// 准备收集当前行答案
			arr[off] = 1;// 每一行第一个是1
			row.add(1);
			for (int j = off + 1; j < i + off - 1; j++) {// 当前行除去首尾的一般部分
				arr[j] = arr[j - i] + arr[j - i + 1];// 一般位置的状态转移
				row.add(arr[j]);
			}
			arr[i + off - 1] = 1;// 每一行最后一个是1
			row.add(1);
			off += i; // 更新偏移量
			ans.add(row);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution118 so = new Solution118();
		so.generate(5);

	}

}
